def max_subarray(nums):
    """
    Kadane算法 - 最大子数组和
    """
    if not nums:
        return 0
    
    # dp[i] 表示以第i个元素结尾的最大子数组和
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    max_sum = nums[0]
    
    # 记录子数组的起始和结束位置
    start = end = 0
    temp_start = 0
    
    for i in range(1, n):
        # 要么延续前面的子数组，要么重新开始
        if dp[i-1] > 0:
            dp[i] = dp[i-1] + nums[i]
        else:
            dp[i] = nums[i]
            temp_start = i
        
        # 更新最大值和位置
        if dp[i] > max_sum:
            max_sum = dp[i]
            start = temp_start
            end = i
    
    return max_sum, nums[start:end+1]

# 测试
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, subarray = max_subarray(nums)

print(f"\n最大子数组和：")
print(f"数组: {nums}")
print(f"最大和: {max_sum}")
print(f"最大子数组: {subarray}")

# 空间优化版本
def max_subarray_optimized(nums):
    if not nums:
        return 0
    
    current_sum = max_sum = nums[0]
    
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    
    return max_sum

print(f"优化版本结果: {max_subarray_optimized(nums)}")